The present invention relates to electronic CAD/CAM systems. In particular the invention relates to layout problems in computer-aided circuit design.
Use of computer-aided design and manufacturing tools and methods have dramatically increased the complexity and sophistication of electronic devices, while decreasing the amount of time and manpower required to develop these circuits. These tools have been used in the design and manufacturing of the most complicated electrical devices, such as integrated circuits, to larger multi-chip modules, to even larger printed circuit boards combining hundreds of discrete components having thousands of intricate connections. Typical integrated circuit microprocessors may have millions of transistors with millions of interconnections, all located within very small areas.
CAD/CAM design tools must solve a variety of problems in designing these complex devices. First, an electronics designer must construct the logical flow of signals into and out of the device, which the CAD/CAM system must then optimize into a series of interconnected discrete components. The discrete components are chosen to be manufacturable (in the case of integrated circuits) by a series of complementary processes onto a single semiconductor substrate. However, given strong competitive trends towards faster, smaller, energy conserving chips and other electronic devices, merely rendering the number, type and interconnections of the components alone is not satisfactory. CAD/CAM design systems must also optimize the placement of circuit elements, whether in an integrated circuit, or on a printed circuit board. Such optimization typically involves compacting the individual devices (or "objects") within the allotted area, while minimizing the number and length of the interconnections. By optimizing circuit compaction, the CAD/CAM system can increase the number of components per unit area, while balancing the power consumption and heat generation of the circuitry. The reduction in interconnection length also increases the speed of signal travel through the circuit, increasing the speed of the device.
A number of attempts at compaction of these devices have been made. Several existing approaches include branch-and-bound methods that use brute force to enumerate the permutations of object locations and calculating costs of different placements. These methods are unfortunately very costly in time and the numbers of calculations required, and often cannot handle arbitrarily-shaped objects. Simulated annealing methods provide an improvement over the random placement approach by moving objects according to a Boltzmann distribution. Convex optimization methods are wire-length (interconnection) driven: first, all interconnections are minimized and then each object is pushed apart until there are no overlaps. Slicing-tree optimization can also used, whereby the area for placement is continually sliced into smaller areas until each object fits into exactly one area. This method is useful for rectangular shaped objects, but not for general shapes or for including wire-length calculations.
Current methods for compaction and placement optimization of electrical devices do not provide a simple and flexible method for handling irregularly shaped objects. These current methods do not provide accurate results while minimizing the computation time required. In addition, many of the methods solve only one portion of the compaction problem, such as minimizing compaction area or minimizing interconnection lengths, but do not provide an overall approach for optimizing all aspects of the layout problem. What is needed is an improved method and apparatus for optimizing the layout of electrical components. An improved technique for two-dimensional compaction should provide a simple, inexpensive and time-economical approach for quickly compacting any number of devices. The improved apparatus and method should provide a flexible approach that easily adapts to any particular problem, and that is readily applicable to integrate circuit design, multi-chip modules layout and printed circuit board arrangements.